package getLeastNumbers;

import java.util.Arrays;

public class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if(k>=arr.length)return arr;
        // 快速选择算法
        return quickSelect(arr, 0,arr.length-1,k);
    }
    private int[] quickSelect(int[] arr,int l,int r,int k) {
        int pivotPos = partrtion(arr,l,r);
        if(pivotPos>k) return quickSelect(arr,l,pivotPos-1,k);
        if(pivotPos<k) return quickSelect(arr,pivotPos+1,r,k);
        return Arrays.copyOf(arr,k);
    }
    private int partrtion(int[] arr,int l,int r) {
        // 选择pivot 点是元素k
        int pivot = arr[l];
        while (l<r) {
            while (l<r && arr[r]>=pivot)r--;
            arr[l] = arr[r];
            while (l<r && arr[l]<=pivot)l++;
            arr[r] = arr[l];
        }
        arr[l] = pivot;
        return l;
    }
}
